﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

public class Solution287
{
    public int FindDuplicate1(int[] nums)
    {

        for (int i = 0; i < nums.Length; i++)
        {
            //使用当前数字作为要标记的index
            int curNum = nums[i];
            if(curNum < 0)
            {
                curNum=-curNum;
            }


           


            if (nums[curNum] < 0)//这个数被标记过了，说明遇到过了
            {

                return curNum;

            }
            else
            {
                nums[curNum] = -nums[curNum];// curNum在1-n之间，不会越界
            }






        }

        return -1;

    }
    public int FindDuplicate2(int[] nums)
    {
        int len=nums.Length;//n+1

        //这些数的范围是1-n
        int left = 1;
        int right = len-1;//n

       
        int res = 0;

        while (left <= right)
        {
            int mid = (left + right) / 2;
            int cnt = 0;//大于mid有多少
            for (int i = 0; i < nums.Length; i++)
            {
                //使用当前数字作为要标记的index
                int curNum = nums[i];
                if (curNum< mid)//小于当前数字的应该有几个
                {
                    cnt++;
                }



            }
            if (cnt<mid)//小于自己（2）的数应该有1个（1）
            {//重复数在右边

                res = mid;
                left = mid + 1;
            }
            else//重复数在左边
            {
                right = mid - 1;
            }
           

        }


        return res;

    }
    //快慢指针
    public int FindDuplicate(int[] nums)
    {

        int low = nums[0];
        int fast = nums[nums[0]];


        while (low != fast) {
            Console.WriteLine("low:  " + low + "  fast:  " + fast );


            low = nums[low];

            fast = nums[nums[fast]];

        }

        low = 0;

        while (low != fast)
        {
            Console.WriteLine("low:  " + low + "  fast:  " + fast);


            low = nums[low];

            fast = nums[nums[fast]];

        }
        return low;
    
    
    }


    }

class Program287
{


    static void Main287(string[] args)
    {

        int[] nums = [1, 3, 4, 2, 2];
        Solution287 solution = new Solution287();
       int res= solution.FindDuplicate(nums);
        Console.WriteLine(res);


    }
}